#include<bits/stdc++.h>
#define mkpr(x, y) make_pair(x, y)
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while(ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while(ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}
int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while(x);
	while (__top) putchar(__stk[__top--] + '0');
}
bool stmer;
const int N = 1520, inf = 1e9;
const double eps = 1e-6;
int n, m, cnt, flag;
int ans[N];
string s;
struct AC {
    int ch[10], fail;
    double sum, cnt;
} t[N];
struct DP {
    double mx; int pre, col;
    DP operator * (const DP &p) const {
        return mx > p.mx ? (DP) {mx, pre, col} : p;
    }
} f[N][N];
void add(string p, double val) {
    int x = 0;
    for(int i = 0; i < p.size(); i++) {
        int op = p[i] - '0';
        if(!t[x].ch[op]) t[x].ch[op] = ++cnt;
        x = t[x].ch[op];
    }
    t[x].sum += val, t[x].cnt += 1;
}
void init_AC() {
    queue<int> q;
    for(int i = 0; i < 10; i++) if(t[0].ch[i]) q.push(t[0].ch[i]);
    while(!q.empty()) {
        int x = q.front(); q.pop();
        for(int i = 0; i < 10; i++) {
            int to = t[x].ch[i], fail = t[t[x].fail].ch[i];
            if(to) t[to].fail = fail, q.push(to);
            else t[x].ch[i] = fail;
        }
        t[x].sum += t[t[x].fail].sum, t[x].cnt += t[t[x].fail].cnt;
        // cout << x << ' ' << t[x].fail << " " << t[x].sum << " " << t[x].cnt << '\n';
    }
}
int vis[N][N], tot;
void work(double d) {
    queue<pair<int, int>> q;
    tot++, q.push(mkpr(0, 0)), vis[0][0] = tot;
    while(!q.empty()) {
        int x = q.front().first, y = q.front().second;
        q.pop(), f[x][y].mx += t[x].sum - d * t[x].cnt;
        double val = f[x][y].mx;
        // if(tmp == 3) cout << x << " " << y << " " << val << " " << d << '\n';
        if(y == n) {
            if(val > 0) {
                flag = 1;
                // cout << x << " " << y << " " << val << " " << d << '\n';
                for(int i = 0; i < n; i++) ans[i] = f[x][y].col, x = f[x][y].pre, y--;
                // for(int i = 1; i <= n; i++) putchar(ans[n - i] + '0'); putchar('\n');
                return;
            } 
            continue;
        } y++;
        if(s[y - 1] == '.') {
            for(int i = 0; i < 10; i++) {
                int to = t[x].ch[i];
                if(vis[to][y] ^ tot) vis[to][y] = tot, f[to][y] = {-inf, 0, 0}, q.push(mkpr(to, y));
                f[to][y] = f[to][y] * (DP) {val, x, i};
            }
        }
        else {
            int to = t[x].ch[s[y - 1] - '0'];
            if(vis[to][y] ^ tot) vis[to][y] = tot, f[to][y] = {-inf, 0, 0}, q.push(mkpr(to, y));
            f[to][y] = f[to][y] * (DP) {val, x, s[y - 1] - '0'};
        }
    }
}
bool edmer;
signed main() {
	freopen("magic.in", "r", stdin);
	freopen("magic.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";
	n = read(), m = read(), cin >> s; string ch;
    for(int i = 1; i <= m; i++) {
        cin >> ch;
        double x = read();
        x = log2l(x), add(ch, x);
    }
    init_AC(); double l = 1, r = 32;
    while(l + eps <= r) {
        double mid = (l + r) / 2.0;
        flag = 0, work(mid), flag ? l = mid + eps : r = mid - eps;
    }
    for(int i = 1; i <= n; i++) putchar(ans[n - i] + '0');
    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds";
	return 0;
} 